import java.util.*;

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val){
        this.val = val;
    }
}

public class Test {
    /*
    题目 1 ：链表的排序
     */
        public static ListNode sortInList (ListNode head) {
            // write code here
            if (head == null || head.next == null)
                return head;
            // 使用快慢指针寻找链表的中点
            ListNode fast = head.next, slow = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode tmp = slow.next;
            slow.next = null;
            // 递归左右两边进行排序
            ListNode left = sortInList(head);
            ListNode right = sortInList(tmp);
            // 创建新的链表
            ListNode h = new ListNode(0);
            ListNode res = h;
            // 合并 left right两个链表
            while (left != null && right != null) {
                // left  right链表循环对比
                if (left.val < right.val) {
                    h.next = left;
                    left = left.next;
                } else {
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            // 最后添加未对比的链表部分判断左链表是否为空
            h.next = left != null ? left : right;
            return res.next;
        }

    public static void main1(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(1);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        ListNode node = sortInList(node1);
    }

    /*
    题目 2：链表内指定区间的反转
     */
    public static ListNode reverseBetween (ListNode head, int m, int n) {
        //设置一个辅助结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        head = dummyNode;

        ListNode frontNode = head;
        ListNode lastNode = head;

        for(int i = 0; i < m - 1; i++){
            frontNode = frontNode.next;
        }

        ListNode fistNode = frontNode.next;

        for(int i = 0; i <= n; i++){
            lastNode = lastNode.next;
        }

        int len = n - m + 1;

        while(len > 0){
            ListNode node = new ListNode(fistNode.val);
            node.next = lastNode;
            lastNode = node;
            fistNode = fistNode.next;
            len--;
        }

        frontNode.next = lastNode;

        return dummyNode.next;
    }

    /*
    题目 3：链表中的节点每 k 个一组翻转
     */
    public static ListNode reverseKGroup (ListNode head, int k) {
        //递归
        ListNode tail = head;

        for(int i = 0; i < k; i++){
            //链表长度不够 k 的，不进行反转！
            if(tail == null){
                return head;
            }
            tail = tail.next;
        }

        //在原来的基础上进行修改
        //每一组翻转的结尾，都是 null ！
        ListNode pre = null;
        ListNode cur = head;
        while(cur != tail){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        head.next = reverseKGroup(tail, k);
        return pre;
    }

    /*
    题目 4 ：判断链表中是否有环
     */
    //思路:快慢指针!
    //快指针走两步,而慢指针走一步
    //在没有环的情况下,每一次移动,快慢指针之间的距离都会 +1 !
    //但如果有环,快指针先进入环,慢指针后进入环,两指针之间的距离先增大,后面随着 快指针再一次入环,两者距离每次移动减少 1 !!这样一定能相遇!!
    public static boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        // 当列表有两个或以上的节点才会进入循环
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    /*
    题目5 ：删除链表的倒数第 n 个节点
     */
    //使用快慢指针！
    public static ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode pre = dummyNode;

        ListNode slow = head;
        ListNode fast = head;

        while(n > 0){
            fast = fast.next;
            n--;
        }

        while(fast != null){
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = slow.next;
        return dummyNode.next;
    }

    /*
    题目 6：删除有序链表中重复的元素Ⅱ
     */
    //直接比较删除
    public static ListNode deleteDuplicates (ListNode head) {
        if(head == null){
            return head;
        }

        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;

        while(cur.next != null && cur.next.next != null){
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                while(cur.next != null && cur.next.val == temp){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return res.next;
    }
}
